#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: min_tree.py 
@version:
@time: 2024/01/14

所谓最小生成树，就是保证图中所有顶点相互连通，并且路径之和最短的连通子图。

1. 以第一个顶点为初始顶点，所有顶点集合为point，已经找到最短路径的顶点集合为visited，到各个顶点的最短路径长度集合为length，length的初始值为第一个顶点到各个顶点的距离。
如果visited列表中已经有某一顶点，则对象的length值为-1，表示无须对该顶点再做考虑，已经找到到该顶点的路径。

2. 找visited集合中的顶点到point-visited集合中顶点的最小边，将这条边加入最小生成树中，同时更新visited与length。

3. 重复执行步骤（2），直至visited中包含图中全部顶点为止。
"""

import sys

MAX = sys.maxsize


def min_tree(graph, point):
    visited = [point[0]]  # 表示已经找到最小生成树中到该顶点边的顶点集合。
    length = [-1]  # 表示visited中的顶点到各个未被访问过的顶点的最小距离集合
    n = len(point)  # 顶点个数
    # 添加
    for i in range(1, n):
        length.append(graph[0][i])
    sum = 0  # 表示最小生成树中边之和
    last = [point[0] for _ in range(n)]  # 表示到每个顶点的最短边的起始端顶点
    # 由于最小生成树中必定包含n个节点及n-1条边，利用一个for循环执行n-1次步骤（2）来确定n-1条边，每次执行过程中，先寻找最短边，并确定最短边的尾节点索引号。
    for _ in range(1, n):
        min = MAX
        min_index = 0
        for j in range(1, n):
            if length[j] != -1 and length[j] < min:
                min = length[j]
                min_index = j
        # 找到最短边之后，相当于又确认了一个顶点，更新visited，length及sum值，同时输出当前边的起点与终点。
        visited.append(min_index)
        sum += length[min_index]
        print(last[min_index], '--', point[min_index])
        length[min_index] = -1
        # 在找到最短边之后，需要更新length列表，若最短边的尾部节点使用length列表中某条边变得更短，要随之更新length与last两个列表，以供下一次执行步骤2
        for j in range(1, n):
            if length[j] != -1 and graph[min_index][j] < length[j]:
                length[j] = graph[min_index][j]
                last[j] = point[min_index]
    return sum


graph1 = [
    [MAX, 10, 12, MAX, MAX, 11, MAX, MAX, 1],
    [10, MAX, MAX, 4, MAX, MAX, 16, MAX, MAX],
    [MAX, 18, MAX, MAX, MAX, 3, MAX, MAX, MAX],
    [MAX, MAX, 20, MAX, 10, MAX, MAX, 11, MAX],
    [18, MAX, MAX, MAX, MAX, MAX, 9, MAX, MAX],
    [MAX, 12, MAX, MAX, MAX, MAX, 11, MAX, MAX],
    [MAX, MAX, MAX, MAX, 27, MAX, MAX, 36, 44],
    [MAX, 3, MAX, MAX, MAX, MAX, 4, MAX, MAX],
    [1, 2, MAX, MAX, 67, MAX, MAX, MAX, 45],
]
point1 = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
res = min_tree(graph1, point1)
print(res)
